﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;




// 堆排序的辅助函数：维护堆的性质
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;    // 将根节点设为最大值
    int left = 2 * i + 1;  // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是根节点
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // 递归地对受影响的子树进行堆化
        heapify(arr, n, largest);
    }
}

//  堆排序
void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 构建最大堆
    for (int i = n/2-1 ; i >= 0; i--)
        heapify(arr, n, i);

    // 逐个提取元素
    for (int i = n - 1; i > 0; i--) {
        // 将当前根节点（最大值）移到末尾
        swap(arr[0], arr[i]);

        // 对剩余元素调用heapify，维持堆性质
        heapify(arr, i, 0);
    }
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}


int main()
{
    vector<int> arr = { 12, 11, 13, 5, 6, 7, 4, 14 };

    // 测试堆排序
    vector<int> heapArr = arr;
    heapSort(heapArr);
    cout << "堆排序后: ";
    printArray(heapArr);
    
    return 0;
}